這是什麼？

探討多個點之間如何聯繫，例如最快速抵達某點？聯繫之間可以補上參數，進而修改最佳路徑。

是不是很有既視感？Google Map 的確使用 Graph 內的演算法：A* algorithm（唸作 A star）。

常見的圖有這幾種：

基本款

加權圖（Weighted Graph）

有向圖（Directed Graph）- 單方向

有向圖（Directed Graph）- 雙方向

表示方法

有兩種，採用矩陣（二維陣列）或是 Linked List，以下都以基本款為例：

相鄰矩陣法（Adjacency Matrix）

  _ 0___1___2___3___4___5
0|  0   1   0   0   1   0
 |
1|  1   0   1   1   0   0
 |
2|  0   1   0   1   0   1
 |
3|  0   1   1   0   1   1
 |
4|  1   0   0   1   0   1
 |
5|  0   0   1   1   0   0

相鄰串列法（Adjacency Linked List）

V0 -> 1 -> 4 -> null
V1 -> 0 -> 2 -> 3 -> null
V2 -> 1 -> 3 -> 5 -> null
V3 -> 1 -> 2 -> 4 -> 5 -> null
V4 -> 0 -> 3 -> null
V5 -> 2 -> 3 -> null

鑑於昨天的經驗，有了基本知識後就來刷題，學習實際做法，避免太高深理論的內容。

刷題：997. Find the Town Judge

題目

In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

1. The town judge trusts nobody.
2. Everybody (except for the town judge) trusts the town judge.
3. There is exactly one person that satisfies properties 1 and 2.

You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b.

If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1.

Example 1:

Input: N = 2, trust = [[1,2]]
Output: 2

Example 2:

Input: N = 3, trust = [[1,3],[2,3]]
Output: 3

Example 3:

Input: N = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

Example 4:

Input: N = 3, trust = [[1,2],[2,3]]
Output: -1

Example 5:

Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3

Constraints:

• 1 <= N <= 1000
• 0 <= trust.length <= 10^4
• trust[i].length == 2
• trust[i] are all different
• trust[i][0] != trust[i][1]
• 1 <= trust[i][0], trust[i][1] <= N

思考

題目的意思為，先給予 N 表示有幾個人，再給予陣列 trust，trust 內的每個項目陣列，代表項目零信任項目一，最後判斷，是不是有一個人，除了自己之外，被所有村民信任。
簡單來說就是 Directed Graph 的概念，是不是有一個點被所有點連結，另外一點是，該點沒有主動連結到其他人。

解題

JS

/**
 * @param {number} N
 * @param {number[][]} trust
 * @return {number}
 */
const findJudge = (N, trust) => {
  if (N === 1) {
    return N;
  }

  let trustMap = new Array(N + 1).fill(0);

  for (let i = 0; i < trust.length; i++) {
    const pair = trust[i];

    if (trustMap[pair[1]]) {
      trustMap[pair[1]]++;
    } else {
      trustMap[pair[1]] = 1;
    }

    if (trustMap[pair[0]]) {
      trustMap[pair[0]]--;
    } else {
      trustMap[pair[0]] = -1;
    }
  }

  for (let key = 0; key < trustMap.length; key++) {
    if (trustMap[key] === N - 1) {
      return key;
    }
  }

  return -1;
};

Java

class Solution {
    public int findJudge(int N, int[][] trust) {
        if (N == 1) {
            return N;
        }

        int[] trustMap = new int[N + 1];

        for(int i = 0; i < trust.length; i++) {
            int[] pair = trust[i];

            trustMap[pair[0]]--;
            trustMap[pair[1]]++;
        }

        for (int key = 0; key < trustMap.length; key++) {
            if (trustMap[key] == N - 1) {
                return key;
            }
        }

        return -1;
    }
}

C

int findJudge(int N, int **trust, int trustSize, int *trustColSize)
{
    if (N == 1)
    {
        return N;
    }

    int trustMap[10000 + 1] = {0};
    int i, key;

    for (i = 0; i < trustSize; i++) {
        trustMap[trust[i][0]]--;
        trustMap[trust[i][1]]++;
    }

    for (key = 0; key < N + 1; key++) {
        if (trustMap[key] == N - 1) {
            return key;
        }
    }

    return -1;
}

看法

三題做法一樣，建立一個建立 trustMap 表示被信任的次數（或是看成被連結的次數），實作的重點是：

• 某人信任他人，被信任的人的信任次數 +1。
• 某人信任他人，某人的信任次數 -1。

計算完畢後再找尋，信任次數為總人數 N - 1 的就是 Judge。

結論

這次採用先理解相關概念後直接解題的做法，發現解題時不會完全採用 Graph 的專有名詞，反倒是在組裝 Array 時，腦海中總是浮現一張 Graph ，作為如何操作 Array 的參考。